module feng.ds.utils {
    /**
     * 二分查找
     * @param   array   数组
     * @param	target	寻找的目标
     * @param	compare	比较函数
     * @param   start   起始位置
     * @param   end     结束位置
     * @return          目标所在位置（如果该位置上不是目标对象，则该索引为该目标可插入的位置）
     */
    export function binarySearch<T>(array: T[], target: T, compare: (a: T, b: T) => number, start: number, end: number): number {

        start = ~~start;
        end = ~~end;
        if (start == end)
            return start;
        if (compare(array[start], target) >= 0) {
            return start;
        }
        if (compare(array[end], target) < 0) {
            return end;
        }
        var middle = ~~((start + end) / 2);
        if (compare(array[middle], target) < 0) {
            start = middle;
        }
        else {
            end = middle;
        }
        return binarySearch(array, target, compare, start, end);
    }
}